package binary_search.leetcode_287_medium;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,4,2,2};
        findDuplicate(nums);
    }
    /*
        给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）。

        注意该题目的限制，只有在该限制条件下，二分法才有效。

        当数组中存在 > 数组长度的元素时，该方法就没用了。
     */
    public static int findDuplicate(int[] nums) {
        int left = 1;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
